// 有效的数独
class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        bool row[9][10] = {};
        bool col[9][10] = {};
        bool grid[3][3][10] = {};
        for (int i = 0; i < board.size(); i++)
            for (int j = 0; j < board[0].size(); j++)
                if (board[i][j] != '.')
                {
                    int n = board[i][j] - '0';
                    if (row[i][n] || col[j][n] || grid[i / 3][j / 3][n]) return false;
                    row[i][n] = col[j][n] = grid[i / 3][j / 3][n] = true;
                }
        return true;
    }
};
    
// 解数独
class Solution {
    bool row[9][10] = {}, col[9][10] = {}, grid[3][3][10] = {};
public:
    void solveSudoku(vector<vector<char>>& board) {
        for (int i = 0; i < 9; i++)
            for (int j = 0; j < 9; j++)
                if (board[i][j] != '.')
                {
                    int n = board[i][j] - '0';
                    row[i][n] = col[j][n] = grid[i / 3][j / 3][n] = true;
                }
        dfs(board);
    }
    bool dfs(vector<vector<char>>& board)
    {
        for (int i = 0; i < 9; i++)
        {
            for (int j = 0; j < 9; j++)
            {
                if (board[i][j] == '.')
                {
                    for (int k = 1; k < 10; k++)
                    {
                        if (!row[i][k] && !col[j][k] && !grid[i / 3][j / 3][k])
                        {
                            board[i][j] = k + '0';
                            row[i][k] = col[j][k] = grid[i / 3][j / 3][k] = true;
                            if (dfs(board)) return true;
                            board[i][j] = '.';
                            row[i][k] = col[j][k] = grid[i / 3][j / 3][k] = false;
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
};
